package com.example.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * 示例 1：
 * 输入：grid = [
 * ['1','1','1','1','0'],
 * ['1','1','0','1','0'],
 * ['1','1','0','0','0'],
 * ['0','0','0','0','0']
 * ]
 * 输出：1
 * <p>
 * 示例 2：
 * 输入：grid = [
 * ['1','1','0','0','0'],
 * ['1','1','0','0','0'],
 * ['0','0','1','0','0'],
 * ['0','0','0','1','1']
 * ]
 * 输出：3
 */
public class Leetcode200_NumsIsland {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] grid = {
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}};
        System.out.println(solution.numIslands(grid));
    }

    static class Solution {
        public int numIslands(char[][] grid) {
//             return numIslands1(grid);
//            return numIslands2(grid);
             return numIslands3(grid);
        }


        /**
         * Flood fill 算法(DFS)
         * <p>
         * Flood fill 算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典 算法。
         * 其思路类似洪水从一个区域扩散到所有能到达的区域。
         *
         * @param grid
         * @return
         */
        public int numIslands1(char[][] grid) {
            int result = 0;
            int rows = grid.length, columns = grid[0].length;
            if (grid == null || rows == 0 || columns == 0)
                return 0;

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (grid[i][j] == '1') { // 说明找到一个岛屿
                        result++;
                        dfsTraverse(grid, i, j);// dfs递归将它的上下左右是'1'的同化成其他'0'
                    }
                }
            }
            return result;
        }

        /**
         * Flood fill 算法(BFS)
         *
         * @param grid
         * @return
         */
        public int numIslands2(char[][] grid) {
            int result = 0;
            int rows = grid.length, columns = grid[0].length;
            if (grid == null || rows == 0 || columns == 0)
                return 0;

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (grid[i][j] == '1') { // 说明找到一个岛屿
                        result++;
                        bfsTraverse(grid, i, j);// bfs将它的上下左右是'1'的同化成其他'0'
                    }
                }
            }

            return result;
        }

        /**
         * 方法三:并查集
         *
         * @param grid
         * @return
         */
        public int numIslands3(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int row = grid.length;
            int column = grid[0].length;
            UnionFind uf = new UnionFind(grid);

            for (int i = 0; i < row; i++) {
                for (int j = 0; j < column; j++) {
                    if (grid[i][j] == '1') {
                        grid[i][j] = '0';
                        // 处理当前元素的下方元素
                        if (i + 1 < row && grid[i + 1][j] == '1')
                            uf.union(i * column + j, (i + 1) * column + j);
                        // 处理右边
                        if (j + 1 < column && grid[i][j + 1] == '1')
                            uf.union(i * column + j, i * column + (j + 1));
                    }
                }
            }

            return uf.getCount();
        }

        // dfs完成同化
        private void dfsTraverse(char[][] grid, int x, int y) {
            if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == '0')
                return;
            grid[x][y] = '0';
            // 递归当前坐标的上下左右四个位置是否是陆地，是的话就递归同化为'0'
            dfsTraverse(grid, x - 1, y);
            dfsTraverse(grid, x + 1, y);
            dfsTraverse(grid, x, y - 1);
            dfsTraverse(grid, x, y + 1);

        }

        class Point {
            int x;
            int y;

            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }

        private void bfsTraverse(char[][] grid, int x, int y) {
            Queue<Point> queue = new LinkedList<>(); // 队列存储的是在grid的坐标值
            queue.offer(new Point(x, y));

            while (!queue.isEmpty()) {
                Point point = queue.poll();
                x = point.x;
                y = point.y;
                if (0 <= x && x < grid.length && 0 <= y && y < grid[0].length && grid[x][y] == '1') {
                    grid[x][y] = '0';
                    queue.offer(new Point(x - 1, y));
                    queue.offer(new Point(x + 1, y));
                    queue.offer(new Point(x, y - 1));
                    queue.offer(new Point(x, y + 1));
                }
            }
        }


        class UnionFind {
            int[] parent;
            int[] rank;
            int count;

            public UnionFind(char[][] grid) {
                this.count = 0;
                int row = grid.length;
                int column = grid[0].length;

                parent = new int[row * column];
                rank = new int[row * column];
                for (int i = 0; i < row; i++) {
                    for (int j = 0; j < column; j++) {
                        if (grid[i][j] == '1') {
                            parent[i * column + j] = i * column + j;
                            count++;
                        }
                        rank[i * column + j] = 0;
                    }
                }
            }

            public int find(int p) {
                //路劲压缩算法,不处理rank
                while (p != parent[p]) {
                    parent[p] = parent[parent[p]];
                    p = parent[p];
                }
                return p;
            }

            public void union(int p, int q) {
                int proot = find(p);
                int qroot = find(q);

                if (proot == qroot)
                    return;
                if (rank[proot] < rank[qroot]) {
                    parent[proot] = qroot;
                } else if (rank[proot] > rank[qroot]) {
                    parent[qroot] = proot;
                } else {
                    parent[qroot] = proot;
                    rank[proot] += 1;
                }
                --count;
            }

            public int getCount() {
                return this.count;
            }

        }

    }
}
